{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Android Unlock Patterns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfPatterns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安卓系统手势解锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们都知道安卓有个手势解锁的界面，是一个&nbsp;<code>3 x 3</code><strong> </strong>的点所绘制出来的网格。用户可以设置一个 “解锁模式” ，通过连接特定序列中的点，形成一系列彼此连接的线段，每个线段的端点都是序列中两个连续的点。如果满足以下两个条件，则 <code>k</code> 点序列是有效的解锁模式：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>解锁模式中的所有点 <strong>互不相同</strong> 。</li>\n",
    "\t<li>假如模式中两个连续点的线段需要经过其他点的 <strong>中心</strong> ，那么要经过的点 <strong>必须提前出现</strong> 在序列中（已经经过），不能跨过任何还未被经过的点。\n",
    "\t<ul>\n",
    "\t\t<li>例如，点 <code>5</code> 或 <code>6</code>&nbsp;没有提前出现的情况下连接点 <code>2</code>&nbsp;和 <code>9</code>&nbsp;是有效的，因为从点 <code>2</code> 到点 <code>9</code> 的线没有穿过点 <code>5</code> 或 <code>6</code> 的中心。</li>\n",
    "\t\t<li>然而，点 <code>2</code> 没有提前出现的情况下连接点 <code>1</code> 和&nbsp;<code>3</code>&nbsp;是无效的，因为从圆点 <code>1</code> 到圆点 <code>3</code> 的直线穿过圆点 <code>2</code> 的中心。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>以下是一些有效和无效解锁模式的示例：</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/10/12/android-unlock.png\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>无效手势：</strong><code>[4,1,3,6]</code> ，连接点 1 和点&nbsp;3 时经过了未被连接过的&nbsp;2 号点。</li>\n",
    "\t<li><strong>无效手势：</strong><code>[4,1,9,2]</code> ，连接点 1 和点 9 时经过了未被连接过的 5&nbsp;号点。</li>\n",
    "\t<li><strong>有效手势：</strong><code>[2,4,1,3,6]</code> ，连接点 1 和点&nbsp;3 是有效的，因为虽然它经过了点&nbsp;2 ，但是点 2 在该手势中之前已经被连过了。</li>\n",
    "\t<li><strong>有效手势：</strong><code>[6,5,4,1,9,2]</code> ，连接点 1 和点&nbsp;9 是有效的，因为虽然它经过了按键 5 ，但是点&nbsp;5 在该手势中之前已经被连过了。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个整数，分别为 ​​<code>m</code> 和 <code>n</code> ，那么请返回有多少种 <strong>不同且有效的解锁模式 </strong>，是 <strong>至少</strong> 需要经过 <code>m</code> 个点，但是 <strong>不超过</strong> <code>n</code> 个点的。</p>\n",
    "\n",
    "<p>两个解锁模式 <strong>不同</strong> 需满足：经过的点不同或者经过点的顺序不同。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 1, n = 1\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 1, n = 2\n",
    "<strong>输出：</strong>65\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [android-unlock-patterns](https://leetcode.cn/problems/android-unlock-patterns/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [android-unlock-patterns](https://leetcode.cn/problems/android-unlock-patterns/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1', '1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        d={\n",
    "            (1,3):2,\n",
    "            (3,1):2,\n",
    "            (1,7):4,\n",
    "            (7,1):4,\n",
    "            (3,9):6,\n",
    "            (9,3):6,\n",
    "            (7,9):8,\n",
    "            (9,7):8,\n",
    "            (1,9):5,\n",
    "            (9,1):5,\n",
    "            (3,7):5,\n",
    "            (7,3):5,\n",
    "            (2,8):5,\n",
    "            (8,2):5,\n",
    "            (4,6):5,\n",
    "            (6,4):5\n",
    "        }\n",
    "        ans=0\n",
    "        def dfs(x,y,last,s):\n",
    "            nonlocal ans\n",
    "            if x==y:\n",
    "                #print(s)\n",
    "                ans+=1\n",
    "                return \n",
    "            for i in range(1,10):\n",
    "                if i in s:\n",
    "                    continue\n",
    "                if (last,i) in d and d[(last,i)] not in s:\n",
    "                    continue\n",
    "                #print(s,i)\n",
    "                s.add(i)\n",
    "                dfs(x+1,y,i,s)\n",
    "                s.remove(i)\n",
    "        for i in range(m,n+1):\n",
    "            dfs(0,i,-1,set())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        d = {\n",
    "            1: {3: 2, 7: 4, 9: 5},\n",
    "            2: {8: 5},\n",
    "            3: {1: 2, 7: 5, 9: 6},\n",
    "            4: {6: 5},\n",
    "            5: {},\n",
    "            6: {4: 5},\n",
    "            7: {1: 4, 3: 5, 9: 8},\n",
    "            8: {2: 5},\n",
    "            9: {1: 5, 3: 6, 7: 8},\n",
    "        }\n",
    "\n",
    "        v = [0]*10\n",
    "\n",
    "\n",
    "        self.r = 0\n",
    "        def dfs(x, s):\n",
    "            if m <= s <= n:\n",
    "                self.r += 1\n",
    "            if s > n:\n",
    "                return\n",
    "            for y in range(1, 10):\n",
    "                if v[y] == 1:\n",
    "                    continue\n",
    "                if y == x:\n",
    "                    continue\n",
    "                if y in d[x] and v[d[x][y]] == 0:\n",
    "                    continue\n",
    "                v[y] = 1\n",
    "                dfs(y, s+1)\n",
    "                v[y] = 0\n",
    "\n",
    "        for i in range(1, 10):\n",
    "            v[i] = 1\n",
    "            dfs(i, 1)\n",
    "            v[i] = 0\n",
    "        \n",
    "        return self.r\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "    \n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        passes = {\n",
    "            (1, 3): 2,\n",
    "            (3, 9): 6,\n",
    "            (7, 9): 8,\n",
    "            (1, 7): 4,\n",
    "            (1, 9): 5,\n",
    "            (3, 7): 5,\n",
    "            (4, 6): 5,\n",
    "            (2, 8): 5\n",
    "        }\n",
    "        \n",
    "        def dfs(path):\n",
    "            if m<=len(path)<=n:\n",
    "                self.res += 1\n",
    "            elif len(path) > n:\n",
    "                return\n",
    "\n",
    "            for i in range(1, 10):\n",
    "                if i in path:\n",
    "                    continue\n",
    "                if len(path) > 0:\n",
    "                    last = path[-1]\n",
    "                    curr = i\n",
    "                    route = tuple(sorted((last, curr)))\n",
    "                    if route in passes and passes[route] not in path:\n",
    "                        continue\n",
    "                path.append(i)\n",
    "                dfs(path)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs([])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "blocker = {\n",
    "    1:{3:2, 9:5, 7:4},\n",
    "    2:{8:5},\n",
    "    3:{1:2, 9:6, 7:5},\n",
    "    4:{6:5},\n",
    "    5:{},\n",
    "    6:{4:5},\n",
    "    7:{1:4,3:5,9:8},\n",
    "    8:{2:5},\n",
    "    9:{1:5,3:6,7:8}\n",
    "}\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        \n",
    "        def dfs(status, curr_num, count):\n",
    "            if count==n:\n",
    "                return 1\n",
    "            ans = 0 if count<m else 1 # current trace forms a valid pattern or not, depends if count<m\n",
    "            for i in range(1,10):\n",
    "                if status & 1<<i ==0:\n",
    "                    if i not in blocker[curr_num] or (1<<blocker[curr_num][i] & status):\n",
    "                        ans+=dfs(status| (1<<i), i, count+1)\n",
    "            return ans\n",
    "        \n",
    "        res = 0\n",
    "        res += dfs(1<<1, 1, 1)*4\n",
    "        res += dfs(1<<2, 2, 1)*4\n",
    "        res += dfs(1<<5,5,1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        self.res=0\n",
    "        d=[[1,3],[4,6],[7,9],[1,7],[2,8],[3,9],[1,9],[3,7]]\n",
    "        def add(arr,m,n):\n",
    "            if len(arr)>=m and len(arr)<=n:\n",
    "                self.res+=1\n",
    "            if len(arr)>n:\n",
    "                return \n",
    "            if len(arr)==0:\n",
    "                for i in range(1,10,1):\n",
    "                    add(arr+[i],m,n)\n",
    "            if len(arr)>0:\n",
    "                for i in range(1,10,1):\n",
    "                    if i not in arr:\n",
    "                        if (([i,arr[-1]] not in d) and ([arr[-1],i] not in d)) or ((([i,arr[-1]] in d) or ([arr[-1],i] in d)) and ((i+arr[-1])//2 in arr)):      \n",
    "                            add(arr+[i],m,n) \n",
    "        add([],m,n) \n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.retNum = 0\n",
    "\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        count = 0\n",
    "        ret = 0\n",
    "        for i in range(m, n + 1):\n",
    "            temp = self.GetCount(i)\n",
    "            #print(temp)\n",
    "            ret += temp\n",
    "        return ret\n",
    "\n",
    "    def GetCount(self, i):\n",
    "        if i == 1:\n",
    "            return 9\n",
    "        elif i == 2:\n",
    "            return 56\n",
    "        # 其他情况\n",
    "\n",
    "        self.GetNext(\"\", i, \"\", \"0100000000\")\n",
    "        ret = self.retNum * 4\n",
    "        self.retNum = 0\n",
    "\n",
    "        self.GetNext(\"\", i, \"\", \"0010000000\")\n",
    "        ret += self.retNum * 4\n",
    "        self.retNum = 0\n",
    "\n",
    "        self.GetNext(\"\", i, \"\", \"0000010000\")\n",
    "        ret += self.retNum\n",
    "        self.retNum = 0\n",
    "\n",
    "        return ret\n",
    "\n",
    "    # currentPosList 是当前走过的\n",
    "    # yeBs 剩下的步数\n",
    "    # lastPos 上一个点\n",
    "    # canUsePos 可以用的点\n",
    "    def GetNext(self, oldCurrentPosList, yeBs, lastPos, canUsePos):\n",
    "        #print(\"%s %i %s %s\" % (oldCurrentPosList, yeBs, lastPos, canUsePos))\n",
    "        oldCanUsePosList = [char for char in canUsePos]\n",
    "        if yeBs == 0:\n",
    "            #print(oldCurrentPosList)\n",
    "            self.retNum += 1\n",
    "            return\n",
    "        yeBs -= 1\n",
    "        for i in range(1, len(oldCanUsePosList)):\n",
    "            #print(\"%i %s\" % (i, canUsePos))\n",
    "            if oldCanUsePosList[i] == \"1\":  # 可用\n",
    "                curPos = str(i)  # 当前走的点\n",
    "                currentPosList = oldCurrentPosList + curPos\n",
    "                lastPos = curPos\n",
    "\n",
    "                # 更新canUsePos\n",
    "                # 重置canUsePosList\n",
    "                canUsePosList = [\"0\", \"1\", \"1\", \"1\", \"1\", \"1\", \"1\", \"1\", \"1\", \"1\"]\n",
    "                for temp in currentPosList:\n",
    "                    canUsePosList[int(temp)] = \"0\"  # 更新已走过的点 走过了不能走\n",
    "\n",
    "                if curPos == \"1\":\n",
    "                    # 1的点对应为 3,7,9不能直接走\n",
    "                    canUsePosList[3] = canUsePosList[7] = canUsePosList[9] = \"0\"\n",
    "                    if (\"3\" not in currentPosList) and (\"2\" in currentPosList):\n",
    "                        canUsePosList[3] = \"1\"\n",
    "                    if (\"7\" not in currentPosList) and (\"4\" in currentPosList):\n",
    "                        canUsePosList[7] = \"1\"\n",
    "                    if (\"9\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[9] = \"1\"\n",
    "                elif curPos == \"2\":\n",
    "                    # 2的点对应为 8不能直接走\n",
    "                    canUsePosList[8] = \"0\"\n",
    "                    if (\"8\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[8] = \"1\"\n",
    "                elif curPos == \"3\":\n",
    "                    # 3的点对应为 1,7,9不能直接走\n",
    "                    canUsePosList[1] = canUsePosList[7] = canUsePosList[9] = \"0\"\n",
    "                    if (\"1\" not in currentPosList) and (\"2\" in currentPosList):\n",
    "                        canUsePosList[1] = \"1\"\n",
    "                    if (\"7\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[7] = \"1\"\n",
    "                    if (\"9\" not in currentPosList) and (\"6\" in currentPosList):\n",
    "                        canUsePosList[9] = \"1\"\n",
    "                elif curPos == \"4\":\n",
    "                    # 4的点对应为 6不能直接走\n",
    "                    canUsePosList[6] = \"0\"\n",
    "                    if (\"6\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[6] = \"1\"\n",
    "                elif curPos == \"6\":\n",
    "                    # 6的点对应为 4不能直接走\n",
    "                    canUsePosList[4] = \"0\"\n",
    "                    if (\"4\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[4] = \"1\"\n",
    "                elif curPos == \"7\":\n",
    "                    # 7的点对应为 1,3,9不能直接走\n",
    "                    canUsePosList[1] = canUsePosList[3] = canUsePosList[9] = \"0\"\n",
    "                    if (\"1\" not in currentPosList) and (\"4\" in currentPosList):\n",
    "                        canUsePosList[1] = \"1\"\n",
    "                    if (\"3\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[3] = \"1\"\n",
    "                    if (\"9\" not in currentPosList) and (\"8\" in currentPosList):\n",
    "                        canUsePosList[9] = \"1\"\n",
    "                elif curPos == \"8\":\n",
    "                    # 8的点对应为 2不能直接走\n",
    "                    canUsePosList[2] = \"0\"\n",
    "                    if (\"2\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[2] = \"1\"\n",
    "                elif curPos == \"9\":\n",
    "                    # 9的点对应为 1,3,7不能直接走\n",
    "                    canUsePosList[1] = canUsePosList[3] = canUsePosList[7] = \"0\"\n",
    "                    if (\"1\" not in currentPosList) and (\"5\" in currentPosList):\n",
    "                        canUsePosList[1] = \"1\"\n",
    "                    if (\"3\" not in currentPosList) and (\"6\" in currentPosList):\n",
    "                        canUsePosList[3] = \"1\"\n",
    "                    if (\"7\" not in currentPosList) and (\"8\" in currentPosList):\n",
    "                        canUsePosList[7] = \"1\"\n",
    "                canUsePos = \"\".join(canUsePosList)\n",
    "\n",
    "                # if currentPosList == \"241\":\n",
    "                #     print(curPos)\n",
    "                #     print(canUsePos)\n",
    "\n",
    "                self.GetNext(currentPosList, yeBs, lastPos, canUsePos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        graph = {\n",
    "            1: {3: 2, 7: 4, 9: 5},\n",
    "            2: {8: 5},\n",
    "            3: {1: 2, 7: 5, 9: 6},\n",
    "            4: {6: 5},\n",
    "            5: {},\n",
    "            6: {4: 5},\n",
    "            7: {1: 4, 3: 5, 9: 8},\n",
    "            8: {2: 5},\n",
    "            9: {1: 5, 3: 6, 7: 8},\n",
    "        }\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(num, n_scan):\n",
    "            if n_scan == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0 if n_scan < m else 1\n",
    "            visited.add(num)\n",
    "            for i in range(1, 10):\n",
    "                cross = graph[num].get(i)\n",
    "                if i in visited or (cross is not None and cross not in visited): continue\n",
    "                res += dfs(i, n_scan + 1)\n",
    "            \n",
    "            visited.remove(num)\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        ans += dfs(1, 1) * 4\n",
    "        ans += dfs(2, 1) * 4\n",
    "        ans += dfs(5, 1)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "block = {(0, 2): 1, (2, 0): 1, (2, 8): 5, (8, 2): 5, (6, 8): 7, (8, 6): 7, (6, 0): 3, (0, 6): 3,\n",
    "         (3, 5): 4, (5, 3): 4, (1, 7): 4, (7, 1): 4, (8, 0): 4, (0, 8): 4, (2, 6): 4, (6, 2): 4}\n",
    "an = tuple(range(9))\n",
    "# dp = {((i, ), an[:i] + an[i + 1:], i): 1 for i in range(9)}\n",
    "dp = {(0, None): 1}\n",
    "res = [0] * 10\n",
    "M = (1 << 9) - 1\n",
    "\n",
    "for i in range(1, 10):\n",
    "    tdp = collections.defaultdict(int)\n",
    "    for (used, now), v in dp.items():\n",
    "        # print(used, unuse, now, v)\n",
    "        for ni in range(9):\n",
    "            if used & (1 << ni): continue\n",
    "            if (now, ni) in block and (1 << block[now, ni]) & used == 0: continue\n",
    "            tdp[used | (1 << ni), ni] += v\n",
    "    res[i] = sum(tdp.values())\n",
    "    dp = tdp\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        return sum(res[m: n + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        dad = {(1, 3):2, (4, 6):5, (7, 9):8, (1, 7):4, (3, 9):6, (1, 9):5, (3, 7):5, \n",
    "        (3, 1):2, (6, 4):5, (9, 7):8, (7, 1):4, (9, 3):6, (9, 1):5, (7, 3):5, (2, 8):5, (8, 2):5}\n",
    "\n",
    "        def isgood(num1, num2, finded):\n",
    "            if (num1, num2) in dad:\n",
    "                if (finded >> dad[(num1, num2)]) & 1:\n",
    "                    return True\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        def mylen(num):\n",
    "            ans = 0\n",
    "            while num:\n",
    "                ans += (num & 1)\n",
    "                num >>= 1\n",
    "            return ans\n",
    "\n",
    "        self.ans = 0\n",
    "\n",
    "        # @cache\n",
    "        def dfs(num, finded):\n",
    "            if m <= mylen(finded) <= n:\n",
    "                self.ans += 1\n",
    "            if mylen(finded) > n:\n",
    "                return 0\n",
    "            t = 0\n",
    "            for next in range(1, 10):\n",
    "                if isgood(num, next, finded) and not ((finded >> next) & 1):\n",
    "                    t += dfs(next, finded | (1 << next))\n",
    "            \n",
    "            return t\n",
    "        for i in range(1, 10):\n",
    "            dfs(i, 1 << (i))\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "\n",
    "        dd = [(-2,-1), (-2, 1),\n",
    "              (-1,-2), (-1,-1), (-1, 0), (-1, 1), (-1, 2),\n",
    "              (0, -1), (0, 1), (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),\n",
    "              (2, -1), (2, 1)]\n",
    "\n",
    "        def backtrack(prev, n, vis):\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            if prev == 0:\n",
    "                return 9+sum(backtrack(cur, n-1, set([cur])) for cur in range(1, 10))\n",
    "\n",
    "            ret = 0\n",
    "\n",
    "            x, y = (prev - 1) // 3, (prev - 1) % 3\n",
    "\n",
    "            for dx, dy in dd:\n",
    "                for k in range(1, 3):\n",
    "                    xx = x + k*dx\n",
    "                    yy = y + k*dy\n",
    "                    if xx < 0 or yy < 0 or xx >= 3 or yy >= 3:\n",
    "                        break\n",
    "                    cur = 3*xx + yy + 1\n",
    "                    if cur in vis:\n",
    "                        continue\n",
    "                    vis.add(cur)\n",
    "                    ret += 1 + backtrack(cur, n-1, vis)\n",
    "                    vis.remove(cur)\n",
    "                    break\n",
    "        \n",
    "            return ret\n",
    "\n",
    "        return backtrack(0, n, None) - backtrack(0, m-1, None)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "\n",
    "        obs = {\n",
    "            -1: {},\n",
    "            1: {\n",
    "                3: 2,\n",
    "                7: 4,\n",
    "                9: 5\n",
    "            },\n",
    "            2: {\n",
    "                8:5\n",
    "            },\n",
    "            3: {\n",
    "                1: 2,\n",
    "                9: 6,\n",
    "                7:5\n",
    "            },\n",
    "            4: {\n",
    "                6:5\n",
    "            },\n",
    "            5: {\n",
    "\n",
    "            },\n",
    "            6: {\n",
    "                4: 5\n",
    "            },\n",
    "            7: {\n",
    "                1: 4,\n",
    "                3: 5,\n",
    "                9: 8\n",
    "            },\n",
    "            8: {\n",
    "                2: 5\n",
    "            },\n",
    "            9: {\n",
    "                1: 5,\n",
    "                7: 8,\n",
    "                3: 6\n",
    "            }\n",
    "        }\n",
    "\n",
    "        self.res = 0\n",
    "        def helper(visited, last):\n",
    "            if len(visited) >= m and len(visited) <= n:\n",
    "                self.res += 1\n",
    "            if len(visited) == n:\n",
    "                return\n",
    "            \n",
    "            cur = 0\n",
    "\n",
    "            for i in range(1, 10):\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                if i in obs[last] and obs[last][i] not in visited:\n",
    "                    continue\n",
    "                visited.add(i)\n",
    "                helper(visited, i)\n",
    "                visited.remove(i)\n",
    "        \n",
    "        helper(set(), -1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "    \n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        passes = {\n",
    "            (1, 3): 2,\n",
    "            (3, 9): 6,\n",
    "            (7, 9): 8,\n",
    "            (1, 7): 4,\n",
    "            (1, 9): 5,\n",
    "            (3, 7): 5,\n",
    "            (4, 6): 5,\n",
    "            (2, 8): 5\n",
    "        }\n",
    "        \n",
    "        def dfs(path):\n",
    "            if m<=len(path)<=n:\n",
    "                self.res += 1\n",
    "            elif len(path) > n:\n",
    "                return\n",
    "\n",
    "            for i in range(1, 10):\n",
    "                if i in path:\n",
    "                    continue\n",
    "                if len(path) > 0:\n",
    "                    last = path[-1]\n",
    "                    curr = i\n",
    "                    route = tuple(sorted((last, curr)))\n",
    "                    if route in passes and passes[route] not in path:\n",
    "                        continue\n",
    "                path.append(i)\n",
    "                dfs(path)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs([])\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "block = {(0, 2): 1, (2, 0): 1, (2, 8): 5, (8, 2): 5, (6, 8): 7, (8, 6): 7, (6, 0): 3, (0, 6): 3,\n",
    "         (3, 5): 4, (5, 3): 4, (1, 7): 4, (7, 1): 4, (8, 0): 4, (0, 8): 4, (2, 6): 4, (6, 2): 4}\n",
    "an = tuple(range(9))\n",
    "# dp = {((i, ), an[:i] + an[i + 1:], i): 1 for i in range(9)}\n",
    "dp = {(0, (1 << 9) - 1, None): 1}\n",
    "res = [0] * 10\n",
    "\n",
    "for i in range(1, 10):\n",
    "    tdp = collections.defaultdict(int)\n",
    "    for (used, unuse, now), v in dp.items():\n",
    "        # print(used, unuse, now, v)\n",
    "        for ni in range(9):\n",
    "            if unuse & (1 << ni) == 0: continue\n",
    "            if (now, ni) in block and (1 << block[now, ni]) & unuse: continue\n",
    "            tdp[used | (1 << ni), unuse ^ (1 << ni), ni] += v\n",
    "    res[i] = sum(tdp.values())\n",
    "    dp = tdp\n",
    "        \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        return sum(res[m: n + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "block = {(0, 2): 1, (2, 0): 1, (2, 8): 5, (8, 2): 5, (6, 8): 7, (8, 6): 7, (6, 0): 3, (0, 6): 3,\n",
    "         (3, 5): 4, (5, 3): 4, (1, 7): 4, (7, 1): 4, (8, 0): 4, (0, 8): 4, (2, 6): 4, (6, 2): 4}\n",
    "dp = {(0, (1 << 9) - 1, None): 1}\n",
    "res = [0] * 10\n",
    "\n",
    "for i in range(1, 10):\n",
    "    tdp = collections.defaultdict(int)\n",
    "    for (used, unuse, now), v in dp.items():\n",
    "        for ni in range(9):\n",
    "            if unuse & (1 << ni) == 0: continue\n",
    "            if (now, ni) in block and (1 << block[now, ni]) & unuse: continue\n",
    "            tdp[used | (1 << ni), unuse ^ (1 << ni), ni] += v\n",
    "        res[i] = sum(tdp.values())\n",
    "        dp = tdp\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        return sum(res[m: n + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        self.ans = 0\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.path = []\n",
    "\n",
    "        visited = set()\n",
    "        for sx in range(1, 10):\n",
    "            visited.add(sx)\n",
    "            self.inner(sx, visited, 1, [sx])\n",
    "            visited.remove(sx)\n",
    "        # print(\"\\n\".join(\"\\t\".join(map(str, p)) for p in self.path))\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "    def inner(self, x, visited, num, path):\n",
    "        if num >= self.m and num <= self.n:\n",
    "            self.ans += 1\n",
    "            # self.path.append(path[:])\n",
    "        if num > self.n:\n",
    "            return\n",
    "        for nx in range(1, 10):\n",
    "            if self.is_valid(visited, x, nx):\n",
    "                visited.add(nx)\n",
    "                # path.append(nx)\n",
    "                self.inner(nx, visited, num+1, path)\n",
    "                # path.pop(-1)\n",
    "                visited.remove(nx)\n",
    "\n",
    "    def is_valid(self, visited, start, end):\n",
    "        if end in visited: return False\n",
    "        # if (start == 1 and end == 3) or (start == 3 and end == 1):\n",
    "        #     return 2 in visited\n",
    "        # if (start == 1 and end == 7) or (start == 7 and end == 1):\n",
    "        #     return 4 in visited\n",
    "        # if (start == 3 and end == 9) or (start == 9 and end == 3):\n",
    "        #     return 6 in visited\n",
    "        # if (start == 7 and end == 9) or (start == 9 and end == 7):\n",
    "        #     return 8 in visited\n",
    "        # if (start == 1 and end == 9) or (start == 9 and end == 1):\n",
    "        #     return 5 in visited\n",
    "        # if (start == 3 and end == 7) or (start == 7 and end == 3):\n",
    "        #     return 5 in visited\n",
    "        # return True\n",
    "\n",
    "        start_row, start_col = (start-1) // 3 , (start-1) % 3\n",
    "        end_row, end_col = (end-1) // 3, (end-1) % 3\n",
    "        if start_row == end_row: # parallel\n",
    "            mid_col = start_col + (end_col - start_col) // 2\n",
    "            mid = start_row * 3 + mid_col + 1\n",
    "            return mid in visited or mid == start or mid == end\n",
    "        elif start_col == end_col: # vertical\n",
    "            mid_row = start_row + (end_row - start_row) // 2\n",
    "            mid = mid_row * 3 + start_col + 1\n",
    "            if start == 2 and end == 8:\n",
    "                print(mid)\n",
    "            return mid in visited or mid == start or mid == end\n",
    "        else:\n",
    "            if (start == 1 and end == 9) or (start == 9 and end == 1):\n",
    "                return 5 in visited\n",
    "            if (start == 3 and end == 7) or (start == 7 and end == 3):\n",
    "                return 5 in visited\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        graph = {\n",
    "            1: {3: 2, 7: 4, 9: 5},\n",
    "            2: {8: 5},\n",
    "            3: {1: 2, 7: 5, 9: 6},\n",
    "            4: {6: 5},\n",
    "            5: {},\n",
    "            6: {4: 5},\n",
    "            7: {1: 4, 3: 5, 9: 8},\n",
    "            8: {2: 5},\n",
    "            9: {1: 5, 3: 6, 7: 8},\n",
    "        }\n",
    "        ans = 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(status, current, count):\n",
    "            if count == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0 if count<m else 1\n",
    "            for i in range(1,10):\n",
    "                if (1<<i)&status==0:\n",
    "                    if i not in graph[current] or (1<<graph[current][i])&status:\n",
    "                        res += dfs(status|(1<<i), i, count+1)\n",
    "            return res\n",
    "\n",
    "        # for cur in range(1, 10):\n",
    "            # ans += dfs(1 << cur, cur, 1)\n",
    "        \n",
    "        ans += 4 * dfs(1 << 1, 1, 1)\n",
    "        ans += 4 * dfs(1 << 2, 2, 1)\n",
    "        ans += dfs(1 << 5, 5, 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "\n",
    "        obs = {1: {3: 2,7: 4,9: 5},\n",
    "            2: {8:5},\n",
    "            3: {1: 2,9: 6,7:5},\n",
    "            4: {6:5},\n",
    "            5: {},\n",
    "            6: {4: 5},\n",
    "            7: {1: 4,3: 5,9: 8},\n",
    "            8: {2: 5},\n",
    "            9: {1: 5,7: 8,3: 6}\n",
    "        }\n",
    "\n",
    "        cache=  {}\n",
    "\n",
    "        def helper(state, last, used):\n",
    "            if (state, last) in cache:\n",
    "                return cache[(state, last)]\n",
    "            if used == n:\n",
    "                return 1\n",
    "            \n",
    "            res = 0 if used < m else 1\n",
    "\n",
    "            for i in range(1, 10):\n",
    "                if state & (1 << i):\n",
    "                    continue\n",
    "                if i in obs[last] and not (state & (1 << obs[last][i])):\n",
    "                    continue\n",
    "                newState = state | (1 << i)\n",
    "                res += helper(newState, i, used + 1)\n",
    "            cache[(state, last)] = res\n",
    "            return res\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(1, 10):\n",
    "            res += helper(1 << i, i, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        graph = {\n",
    "            1: {3: 2, 7: 4, 9: 5},\n",
    "            2: {8: 5},\n",
    "            3: {1: 2, 7: 5, 9: 6},\n",
    "            4: {6: 5},\n",
    "            5: {},\n",
    "            6: {4: 5},\n",
    "            7: {1: 4, 3: 5, 9: 8},\n",
    "            8: {2: 5},\n",
    "            9: {1: 5, 3: 6, 7: 8},\n",
    "        }\n",
    "        ans = 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(status, current, count):\n",
    "            if count == n:\n",
    "                return 1\n",
    "            current_ans = 0 if count < m else 1\n",
    "            for i in range(1, 10):\n",
    "                if status & (1 << i) == 0:\n",
    "                    if i not in graph[current] or ((1 << graph[current][i]) & status):\n",
    "                        current_ans += dfs(status | (1 << i), i, count + 1)\n",
    "            return current_ans\n",
    "\n",
    "        # for cur in range(1, 10):\n",
    "            # ans += dfs(1 << cur, cur, 1)\n",
    "        \n",
    "        ans += 4 * dfs(1 << 1, 1, 1)\n",
    "        ans += 4 * dfs(1 << 2, 2, 1)\n",
    "        ans += dfs(1 << 5, 5, 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#安卓系统手势解锁,输入：m = 1, n = 2输出：65;输入：m = 1, n = 1,输出：9\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        graph = {\n",
    "            1: {3: 2, 7: 4, 9: 5},\n",
    "            2: {8: 5},\n",
    "            3: {1: 2, 7: 5, 9: 6},\n",
    "            4: {6: 5},\n",
    "            5: {},\n",
    "            6: {4: 5},\n",
    "            7: {1: 4, 3: 5, 9: 8},\n",
    "            8: {2: 5},\n",
    "            9: {1: 5, 3: 6, 7: 8},\n",
    "        }\n",
    "        ans = 0\n",
    "        @lru_cache(None)\n",
    "        def dfs(status, current, count):\n",
    "            if count == n:return 1\n",
    "            current_ans = 0 if count < m else 1\n",
    "            for i in range(1, 10):\n",
    "                if status & (1 << i) == 0:\n",
    "                    if i not in graph[current] or ((1 << graph[current][i]) & status):\n",
    "                        current_ans += dfs(status | (1 << i), i, count + 1)\n",
    "            return current_ans\n",
    "        ans += 4 * dfs(1 << 1, 1, 1)\n",
    "        ans += 4 * dfs(1 << 2, 2, 1)\n",
    "        ans += dfs(1 << 5, 5, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        \n",
    "        # d\n",
    "        @cache\n",
    "        def dfs(state, k, prev):\n",
    "            # 输入一个state，01代表选择情况 k 还需要选择k个点\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for p in range(9):\n",
    "                # choose a new point, join into pattern\n",
    "                # requirement: 1 that point is never selected before\n",
    "                # \n",
    "                if state == 0:\n",
    "                    res += dfs(state | 1 << p, k-1, p)\n",
    "                    continue\n",
    "                if state >> p & 1 == 1: # if selected, move on\n",
    "                    continue\n",
    "                x, y = p // 3, p % 3 # for unselected point, get coordinates\n",
    "                # prev\n",
    "                prev_x, prev_y = prev // 3, prev % 3\n",
    "                mid_x, mid_y = (x + prev_x) // 2, (y + prev_y) // 2\n",
    "                mid = mid_x * 3 + mid_y\n",
    "                if (x+prev_x)%2==0 and (y+prev_y)%2==0 and state >> mid & 1 == 0:\n",
    "                    continue\n",
    "                res += dfs(state | 1 << p, k-1, p)\n",
    "                \n",
    "                # for q in range(9):\n",
    "                    # if state >> q & 1 == 0:\n",
    "                        # continue\n",
    "                    # i, j = q // 3, q % 3\n",
    "                    # print(i, x, (i+x)%2, \" * \", j, y, (j+y)%2)\n",
    "                    \n",
    "                    # (0,0) (1,2) -> 0.5, 1 not valid point\n",
    "                    # (1,1) (1,2) -> (1,1) not valid\n",
    "                    # (1,0) (2,2) -> (1.5, 1) not valid \n",
    "                    # (0,0) (2,2) -> (1,1) valid point\n",
    "                    # mid_x, mid_y = (i + x) // 2, (j + y) // 2\n",
    "                    # z = mid_x * 3 + mid_y\n",
    "                    # if (i + x) % 2 == 0 and (j + y) % 2 == 0 and state >> z & 1 == 0:                       \n",
    "                        # continue\n",
    "                    \n",
    "                    # if state >> z & 1 == 0: # mid not in state, invalid case\n",
    "                    #    continue\n",
    "                    # res += dfs(state | 1 << p, k-1)\n",
    "            return res\n",
    "        \n",
    "        return sum(dfs(0, k, -1) for k in range(m, n+1))\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        # 当前是conflict[0]，想要去conflict[1]，必须已经去过conflict[2]\n",
    "        conflict = [[1, 3, 2], [1, 7, 4], [1, 9, 5], [2, 8, 5], [3, 1, 2], [3, 7, 5], [3, 9, 6],\n",
    "        [4, 6, 5], [6, 4, 5], [7, 1, 4], [7, 3, 5], [7, 9, 8], [8, 2, 5], [9, 1, 5], [9, 3, 6],\n",
    "        [9, 7, 8]]\n",
    "\n",
    "        # 当前位于num，还剩下rest个数\n",
    "        @cache\n",
    "        def dfs(num, rest, state):\n",
    "            if rest == 0: return 1\n",
    "            ans = 0\n",
    "            for i in range(1, 10):\n",
    "                if num == i or (state & (1 << i)) > 0: continue\n",
    "                flag = True\n",
    "                for c in conflict:\n",
    "                    if num == c[0] and i == c[1] and (state & (1 << c[2])) == 0:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if not flag: continue\n",
    "                ans += dfs(i, rest - 1, state | (1 << i))\n",
    "            return ans\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m, n + 1):\n",
    "            ans += dfs(0, i, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        iniState = 0\n",
    "        def getRow(state, r):\n",
    "            return (state>>(r*3)) & int('111', 2)\n",
    "        def getCol(state, c):\n",
    "            ret = 0\n",
    "            for r in range(3):\n",
    "                ret<<=1\n",
    "                row = getRow(state, r)\n",
    "                ret += (row>>c)&1\n",
    "            return ret\n",
    "        def validRC(num):\n",
    "            return num != 5\n",
    "        def R(n):\n",
    "            return n//3\n",
    "        def C(n):\n",
    "            return n%3\n",
    "        # def validX(state):\n",
    "        #     if int('100010001', 2) & state == int('100000001', 2): return False\n",
    "        #     if int('001010100', 2) & state == int('001000100', 2): return False\n",
    "        #     return True\n",
    "        def isValidInsert(state, last, new):\n",
    "            last, new = last-1, new-1\n",
    "            if R(last) == R(new) and not validRC(getRow(state, R(last))): return False\n",
    "            if C(last) == C(new) and not validRC(getCol(state, C(last))): return False\n",
    "            if last+new == 8: return (state & int('000010000', 2)) != 0\n",
    "            return True\n",
    "            \n",
    "        def isEmptyPoint(state, new):\n",
    "            return state & (1 << (new-1)) == 0\n",
    "        def insert(state, new):\n",
    "            return state | (1 << (new-1))\n",
    "\n",
    "        # tb = 0\n",
    "        # tb = insert(tb, 1)\n",
    "        # tb = insert(tb, 9)\n",
    "        # print(isValidInsert(tb, 1, 9))\n",
    "        \n",
    "        curStates = collections.deque([(0, -1)])\n",
    "        # print(curStates)\n",
    "        # print(isValidBoard(int('100000001', 2)))\n",
    "        ret = 0\n",
    "        for i in range(1, m):\n",
    "            dqn = len(curStates)\n",
    "            for _ in range(dqn):\n",
    "                iniState, last = curStates.popleft()\n",
    "                for newP in range(1, 10):\n",
    "                    if isEmptyPoint(iniState, newP):\n",
    "                        newState = insert(iniState, newP)\n",
    "                        if last == -1: curStates.append((newState, newP))\n",
    "                        elif isValidInsert(newState, last, newP):\n",
    "                            curStates.append((newState, newP))\n",
    "        # print(curStates)\n",
    "        for i in range(m, n+1):\n",
    "            dqn = len(curStates)\n",
    "            for _ in range(dqn):\n",
    "                iniState, last = curStates.popleft()\n",
    "                for newP in range(1, 10):\n",
    "                    if isEmptyPoint(iniState, newP):\n",
    "                        newState = insert(iniState, newP)\n",
    "                        # print(newState)\n",
    "                        if last == -1: curStates.append((newState, newP))\n",
    "                        elif isValidInsert(newState, last, newP):\n",
    "                            curStates.append((newState, newP))\n",
    "            ret+=len(curStates)\n",
    "        # print(curStates)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        iniState = 0\n",
    "        def getRow(state, r):\n",
    "            return (state>>(r*3)) & int('111', 2)\n",
    "        def getCol(state, c):\n",
    "            ret = 0\n",
    "            for r in range(3):\n",
    "                ret<<=1\n",
    "                row = getRow(state, r)\n",
    "                ret += (row>>c)&1\n",
    "            return ret\n",
    "        def validRC(num):\n",
    "            return num != 5\n",
    "        def R(n):\n",
    "            return n//3\n",
    "        def C(n):\n",
    "            return n%3\n",
    "        # def validX(state):\n",
    "        #     if int('100010001', 2) & state == int('100000001', 2): return False\n",
    "        #     if int('001010100', 2) & state == int('001000100', 2): return False\n",
    "        #     return True\n",
    "        def isValidInsert(state, last, new):\n",
    "            last, new = last-1, new-1\n",
    "            if R(last) == R(new) and not validRC(getRow(state, R(last))): return False\n",
    "            if C(last) == C(new) and not validRC(getCol(state, C(last))): return False\n",
    "            if last+new == 8: return (state & int('000010000', 2)) != 0\n",
    "            return True\n",
    "            \n",
    "        def isEmptyPoint(state, new):\n",
    "            return state & (1 << (new-1)) == 0\n",
    "        def insert(state, new):\n",
    "            return state | (1 << (new-1))\n",
    "\n",
    "        tb = 0\n",
    "        tb = insert(tb, 1)\n",
    "        tb = insert(tb, 9)\n",
    "        print(isValidInsert(tb, 1, 9))\n",
    "        \n",
    "        curStates = collections.deque([(0, -1)])\n",
    "        # print(curStates)\n",
    "        # print(isValidBoard(int('100000001', 2)))\n",
    "        ret = 0\n",
    "        for i in range(1, m):\n",
    "            dqn = len(curStates)\n",
    "            for _ in range(dqn):\n",
    "                iniState, last = curStates.popleft()\n",
    "                for newP in range(1, 10):\n",
    "                    if isEmptyPoint(iniState, newP):\n",
    "                        newState = insert(iniState, newP)\n",
    "                        if last == -1: curStates.append((newState, newP))\n",
    "                        elif isValidInsert(newState, last, newP):\n",
    "                            curStates.append((newState, newP))\n",
    "        # print(curStates)\n",
    "        for i in range(m, n+1):\n",
    "            dqn = len(curStates)\n",
    "            for _ in range(dqn):\n",
    "                iniState, last = curStates.popleft()\n",
    "                for newP in range(1, 10):\n",
    "                    if isEmptyPoint(iniState, newP):\n",
    "                        newState = insert(iniState, newP)\n",
    "                        # print(newState)\n",
    "                        if last == -1: curStates.append((newState, newP))\n",
    "                        elif isValidInsert(newState, last, newP):\n",
    "                            curStates.append((newState, newP))\n",
    "            ret+=len(curStates)\n",
    "        # print(curStates)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "chuan={(1,3):2,(1,7):4,(1,9):5,(2,8):5,(3,1):2,(3,7):5,(3,9):6,(4,6):5,(6,4):5,(7,1):4,(7,3):5,(7,9):8,(8,2):5,(9,7):8,(9,3):6,(9,1):5}\n",
    "c=list(chuan.keys())\n",
    "def way(n):\n",
    "    if n==1:\n",
    "        return [[_] for _ in range(1,10)]\n",
    "    res=[]\n",
    "    for w in way(n-1):\n",
    "        for i in range(1,10):\n",
    "            if i in w: continue\n",
    "            if (w[-1],i) in c and chuan[(w[-1],i)] not in w: continue\n",
    "            res.append(w+[i])\n",
    "    return res\n",
    "lofway=[len(way(_)) for _ in range(1,10)]\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        return sum(lofway[m-1:n])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPatterns(self, m: int, n: int) -> int:\n",
    "        nums=[0]*9\n",
    "        ret=0\n",
    "        ret_exact=[]\n",
    "        def check(last,k):\n",
    "            last=last\n",
    "            k=k\n",
    "            if last+1 in [1,4,7] and k==last+2:\n",
    "                if nums[last+1]==0:\n",
    "                    return False\n",
    "            elif last+1 in [3,6,9] and k==last-2:\n",
    "                if nums[last-1]==0:\n",
    "                    return False\n",
    "            if last+1 in [1,2,3] and k==last+6:\n",
    "                if nums[last+3]==0:\n",
    "                    return False\n",
    "            elif last+1 in [7,8,9] and k==last-6:\n",
    "                if nums[last-3]==0:\n",
    "                    return False\n",
    "            if {last+1,k+1}=={1,9} or {last+1,k+1}=={3,7}:\n",
    "                if nums[4]==0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def dfs(used,last,used_num):\n",
    "            if used_num>=m:\n",
    "                nonlocal ret,ret_exact\n",
    "                ret+=1\n",
    "                temp=[]\n",
    "                for i in range(9):\n",
    "                    if used[i]==1:\n",
    "                        temp.append(i+1)\n",
    "                ret_exact.append(temp)\n",
    "                    \n",
    "            for i in range(9):\n",
    "                if nums[i]!=1:\n",
    "                    if check(last,i) and used_num+1<=n:\n",
    "                        used[i]=1\n",
    "                        dfs(used,i,used_num+1)\n",
    "                        used[i]=0\n",
    "        dfs(nums,10,0)\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
